import java.util.HashMap;

/**
 * @author hewei
 * @version 1.0
 * @description: 873. 最长的斐波那契子序列的长度
 * @date 2022/10/12 15:42
 */

public class LenLongestFibSubseq2 {

    public int lenLongestFibSubseq(int[] arr) {
        HashMap<Integer, Integer> indexMap = new HashMap<>();
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < arr.length; i++) {
            indexMap.put(arr[i], i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0 && arr[j] * 2 > arr[i]; j--) {
                int delta = arr[i] - arr[j];
                Integer index = indexMap.get(delta);
                if (index != null) {
                    dp[i][j] = Math.max(2, dp[j][index] + 1);
                } else dp[i][j] = 1;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans >= 2 ? ans + 1 : 0;
    }
}